package com.lw.leetcode.binary.c;

/**
 * Created with IntelliJ IDEA.
 * 878. 第 N 个神奇数字
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/22 9:18
 */
public class NthMagicalNumber {

    public static void main(String[] args) {
        NthMagicalNumber test = new NthMagicalNumber();

        // 451356
        int n = 100301;
        int a = 6;
        int b = 9;

        int i = test.nthMagicalNumber(n, a, b);
        System.out.println(i);
    }

    private int a;
    private int b;

    public int nthMagicalNumber(int n, int a, int b) {
        this.a = a;
        this.b = b;
        long st = 0;
        long end = Math.min(a, b) * (long) n;
        int t = a * b / gct(a, b);
        while (st <= end) {
            long mid = getMid(st, end);
            long c = mid / a + mid / b - mid / t;
            if (c == n) {
                return (int) (mid % 1000000007);
            }
            if (c < n) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return (int) (st % 1000000007);
    }

    private int gct(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gct(b, a % b);
    }

    private long getMid(long st, long end) {
        long m = st + ((end - st + 1) >> 1);
        long min = Math.max(m / a * a, m / b * b);
        if (min < st) {
            return Math.min((m / a + 1) * a, (m / b + 1) * b);
        }
        return min;
    }

}
